790. Double Queue
The new founded Balkan
Investment Group Bank (BIG-Bank) opened a new office in
0 The system needs to stop serving
1 k p Add client k to the waiting list with priority p
2 Serve the client with the highest
priority and drop him or her from the waiting list
3 Serve the client with the lowest priority
and drop him or her from the waiting list
Your task is to help the software
engineer of the bank by writing a program to implement the requested serving
policy.
Input. Each line of the input contains one of the possible
requests; only the last line contains the stop-request (code 0). You may assume
that when there is a request to include a new client in the list (code 1),
there is no other request in the list of the same client or with the same
priority. An identifier k is always
less than 106, and a priority p
is less than 107. The client may arrive for being served multiple
times, and each time may obtain a different priority.
Output. For each request with code 2
or 3, the program has to print, in a separate line of the standard output, the
identifier of the served client. If the request arrives when the waiting list
is empty, then the program prints zero (0) to the output.
|
Sample input |
Sample output |
|
2 1 20 14 1 30 3 2 1 10 99 3 2 2 0 |
0 20 30 10 0 |
data
structures - set
The client priorities we shall keep in the set s. Then the client with the lowest
priority will be at the beginning of the set, and the client with the greatest
priority at the end of the set. As the priorities of different clients are
different, we can establish a one-to-one correspondence between priorities and
client numbers. We make this by means of an integer array client of length 10000001. If the priority of client is p, then his number will be kept in client[p].
To solve the problem it is enough to simulate the process of
serving the clients.
Store the priorities and
numbers of clients in the queue in the set of pairs s. If a customer with number k and priority p enters the service, then add a pair (p, k) to the set s.
set<pair<int,int> > s;
The main part of the program.
Depending on the type of query, perform the appropriate action. Continue the loop until the
customer service system stops (the code value becomes 0).
while(scanf("%d",&code),
code)
Put the priority and the number of the incoming client in the set s.
if (code == 1)
{
scanf("%d %d",&k,&p);
s.insert(make_pair(p,k));
} else
The client’s highest priority is at the end of the set s.
if (code == 2)
if (s.empty()) printf("0\n");
else
{
iter = s.end(); iter--;
printf("%d\n",(*iter).second);
s.erase(iter);
} else
The client’s lowest priority is at the beginning of the set s.
if (s.empty()) printf("0\n");
else
{
printf("%d\n",(*s.begin()).second);
s.erase(s.begin());
}
Algorithm realization – set of
integers
The client priorities from the waiting list will be stored in
the set s. Their appropriate numbers
will be stored in array client. If
the service receives a client with a number k
and a priority p, we assign client[p] = k.
set<int> s;
int client[10000001];
The main part of the program. Depending on the type of the query,
we produce the appropriate action. Continue the loop until the system of client
service does not stop (until the code will
not become 0).
while(scanf("%d",&code),
code)
Write the client number k into the cell client[p]. Put the
priority of the incoming client into the set s.
if (code ==
1)
{
scanf("%d
%d",&k,&p);
client[p] = k; s.insert(p);
} else
The highest priority of the
client is at the end of the set s.
if (code ==
2)
if
(s.empty()) printf("0\n"); else
{
iter = s.end(); iter--;
printf("%d\n",client[*iter]);
s.erase(iter);
} else
The lowest priority of the
client is at the beginning of the set s.
if
(s.empty()) printf("0\n"); else
{
printf("%d\n",client[*s.begin()]);
s.erase(s.begin());
}
Java realization BufferReader
= 1,2sec
import java.util.*;
import java.io.*;
public class Main
{
public static void main(String[] args)
throws Exception
{
BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
int[] Client = new int[10000001];
int Code;
TreeSet<Integer> s = new TreeSet<Integer>();
String
Line;
while(!(Line =
in.readLine()).equals("0"))
{
StringTokenizer st = new StringTokenizer(Line);
Code
= Integer.parseInt(st.nextToken());
if (Code == 1)
{
int k = Integer.parseInt(st.nextToken()),
p = Integer.parseInt(st.nextToken());
Client[p] = k; s.add(p);
} else
if (Code == 2)
if (s.isEmpty()) System.out.println("0"); else
{
int LastElement =
s.last();
System.out.println(Client[LastElement]);
s.remove(LastElement);
} else
if (s.isEmpty()) System.out.println("0"); else
{
int FirstElement =
s.first();
System.out.println(Client[FirstElement]);
s.remove(FirstElement);
}
}
}
}
Java realization Scanner =
1,4 sec
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner con = new
Scanner(System.in);
int[] Client = new int[10000001];
int Code;
TreeSet<Integer> s = new
TreeSet<Integer>();
while((Code = con.nextInt()) !=
0)
{
if (Code == 1)
{
int k = con.nextInt(), p = con.nextInt();
Client[p] = k; s.add(p);
} else
if (Code == 2)
if (s.isEmpty())
System.out.println("0"); else
{
int LastElement = s.last();
System.out.println(Client[LastElement]);
s.remove(LastElement);
} else
if (s.isEmpty())
System.out.println("0"); else
{
int FirstElement = s.first();
System.out.println(Client[FirstElement]);
s.remove(FirstElement);
}
}
}
}
Java realization FastScanner
= 1 sec
import java.util.*;
import java.io.*;
class FastScanner
{
private BufferedReader
br;
private
StringTokenizer st;
public
FastScanner(InputStreamReader reader)
{
br = new BufferedReader(reader);
}
public String next()
{
while (st == null || !st.hasMoreTokens())
{
try
{
st = new StringTokenizer(br.readLine());
} catch (Exception e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt()
{
return Integer.parseInt(next());
}
public double nextDouble()
{
return Double.parseDouble(next());
}
public void close() throws Exception
{
br.close();
}
}
public class Main
{
public static void main(String[] args)
{
FastScanner con
=
new FastScanner(new InputStreamReader(System.in));
int[] Client = new int[10000001];
int Code;
TreeSet<Integer> s = new TreeSet<Integer>();
while((Code = con.nextInt()) != 0)
{
if (Code == 1)
{
int k = con.nextInt(), p
= con.nextInt();
Client[p] = k; s.add(p);
} else
if (Code == 2)
if (s.isEmpty()) System.out.println("0"); else
{
int LastElement = s.last();
System.out.println(Client[LastElement]);
s.remove(LastElement);
} else
if (s.isEmpty()) System.out.println("0"); else
{
int FirstElement = s.first();
System.out.println(Client[FirstElement]);
s.remove(FirstElement);
}
}
}
}
Java realization – TreeMap
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner con = new
Scanner(System.in);
TreeMap<Integer, Integer> tree = new TreeMap<Integer, Integer>();
while(true)
{
int Code = con.nextInt();
if (Code == 0) break;
if (Code == 1)
{
int k = con.nextInt();
int p = con.nextInt();
tree.put(p,k);
} else
if (Code == 2)
if (tree.isEmpty())
System.out.println("0"); else
{
System.out.println(tree.lastEntry().getValue());
tree.pollLastEntry();
} else
if (tree.isEmpty())
System.out.println("0"); else
{
System.out.println(tree.firstEntry().getValue());
tree.pollFirstEntry();
}
}
con.close();
}
}